/*
 * This file is part of Cadmium.
 * Copyright (C) 2007-2010 Xavier Clerc.
 *
 * Cadmium is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Cadmium is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package fr.x9c.cadmium.primitives.str;

import java.util.LinkedList;
import java.util.List;

import fr.x9c.cadmium.kernel.Block;
import fr.x9c.cadmium.kernel.CodeRunner;
import fr.x9c.cadmium.kernel.Context;
import fr.x9c.cadmium.kernel.Fail;
import fr.x9c.cadmium.kernel.Fatal;
import fr.x9c.cadmium.kernel.Primitive;
import fr.x9c.cadmium.kernel.PrimitiveProvider;
import fr.x9c.cadmium.kernel.Value;
import fr.x9c.cadmium.util.Misc;

/**
 * This class implements all primitives for 'Str' module.
 *
 * @author <a href="mailto:cadmium@x9c.fr">Xavier Clerc</a>
 * @version 1.0
 * @since 1.0
 */
@PrimitiveProvider
public final class Str {

    /** Index of field 'prog' in compiled regexp. */
    private static final int PROG = 0;

    /** Index of field 'cpool' in compiled regexp. */
    private static final int CPOOL = 1;

    /** Index of field 'norm_table' in compiled regexp. */
    private static final int NORM_TABLE = 2;

    /** Index of field 'num_groups' in compiled regexp. */
    private static final int NUM_GROUPS = 3;

    /** Index of field 'num_registers' in compiled regexp. */
    private static final int NUM_REGISTERS = 4;

    /** Index of field 'start_chars' in compiled regexp. */
    private static final int START_CHARS = 5;

    /** Opcode for automaton interpreter. */
    private static final int CHAR = 0;

    /** Opcode for automaton interpreter. */
    private static final int CHARNORM = 1;

    /** Opcode for automaton interpreter. */
    private static final int STRING = 2;

    /** Opcode for automaton interpreter. */
    private static final int STRINGNORM = 3;

    /** Opcode for automaton interpreter. */
    private static final int CHARCLASS = 4;

    /** Opcode for automaton interpreter. */
    private static final int BOL = 5;

    /** Opcode for automaton interpreter. */
    private static final int EOL = 6;

    /** Opcode for automaton interpreter. */
    private static final int WORDBOUNDARY = 7;

    /** Opcode for automaton interpreter. */
    private static final int BEGGROUP = 8;

    /** Opcode for automaton interpreter. */
    private static final int ENDGROUP = 9;

    /** Opcode for automaton interpreter. */
    private static final int REFGROUP = 10;

    /** Opcode for automaton interpreter. */
    private static final int ACCEPT = 11;

    /** Opcode for automaton interpreter. */
    private static final int SIMPLEOPT = 12;

    /** Opcode for automaton interpreter. */
    private static final int SIMPLESTAR = 13;

    /** Opcode for automaton interpreter. */
    private static final int SIMPLEPLUS = 14;

    /** Opcode for automaton interpreter. */
    private static final int GOTO = 15;

    /** Opcode for automaton interpreter. */
    private static final int PUSHBACK = 16;

    /** Opcode for automaton interpreter. */
    private static final int SETMARK = 17;

    /** Opcode for automaton interpreter. */
    private static final int CHECKPROGRESS = 18;

    /** To fake/emulate gotos ... */
    private static final int NO_GOTO = 0;

    /** To fake/emulate gotos ... */
    private static final int GOTO_PREFIX_MATCH = 1;

    /** To fake/emulate gotos ... */
    private static final int GOTO_BACKTRACK = 2;

    /** To fake/emulate gotos ... */
    private static final int GOTO_PUSH = 3;

    /** To fake/emulate gotos ... */
    private static final int GOTO_ACCEPT = 4;

    /** Null / no index. */
    private static final int NULL = -1;

    /** Null / no index as a value. */
    private static final Value NULL_VALUE = Value.MINUS_ONE;

    /** Context slot for groups. */
    private static final Object SLOT_GROUPS = new Object();

    /** End of line, as an ocaml character. */
    private static final int END_OF_LINE =
        Misc.signedToUnsignedByte(Misc.convertCharToByte('\n'));

    /**
     * Indicates whether a character is part of a word
     * (bit vector from character to boolean).
     */
    private static final int[] RE_WORD_LETTERS = {
        0, 0, 0, 0, 0, 0, 0, 0,
        254, 255, 255, 7, 254, 255, 255, 7,
        0, 0, 0, 0, 0, 0, 0, 0,
        255, 255, 127, 255, 255, 255, 127, 255
    };

    /**
     * No instance of this class.
     */
    private Str() {
    } // end empty constructor

    /**
     * Tests whether a character is a word letter.
     * @param ch character to test
     * @return <tt>true</tt> if passed character is a word letter,
     *         <tt>false</tt> otherwise
     */
    private static boolean isWordLetter(final int ch) {
        return ((Str.RE_WORD_LETTERS[ch >> 3] >> (ch & 7)) & 1) != 0;
    } // end method 'isWordLetter(int)'

    /**
     * This class models matched group: start and end offsets of group.
     */
    private static final class ReGroup {

        /** Starting offset of matched group. */
        int idxStart;

        /** Ending offset of matched group. */
        int idxEnd;

        /**
         * Constructs an instance with both offsets set to <tt>NULL</tt>.
         */
        private ReGroup() {
            this.idxStart = Str.NULL;
            this.idxEnd = Str.NULL;
        } // end empty constructor

    } // end inner-class 'ReGroup'

    /**
     * Returns the opcode of an instruction.
     * @param x instruction
     * @return opcode of passed instruction
     */
    private static int opcode(final int x) {
        return x & 0xFF;
    } // end method 'opcode(int)'

    /**
     * Returns the argument of an instruction.
     * @param x instruction
     * @return argument of passed instruction
     */
    private static int arg(final int x) {
        return (int) (Misc.signedToUnsigned(x) >> 8);
    } // end method 'arg(int)'

    /**
     * Returns the signed argument of an instruction.
     * @param x instruction
     * @return signed argument of passed instruction
     */
    private static int signedArg(final int x) {
        return x >> 8;
    } // end method 'signedArg(int)'

    /**
     * Tests presence in a bit vector.
     * @param s bit vector
     * @param idx bit index
     * @return <tt>true</tt> if the corresponding bit is set,
     *         <tt>false</tt> otherwise
     */
    private static boolean inBitSet(final int[] s, final int idx) {
        return ((s[idx >> 3] >> (idx & 7)) & 1) != 0;
    } // end method 'inBitSet(int[], int)'

    /**
     * Runs the matching engine.
     * @param ctxt context
     * @param re compiled regular expression
     * @param str string to match
     * @param idxStartTxt starting index of string
     * @param idx index of string
     * @param idxEndTxt ending index of string
     * @param acceptPartialMatch whether partial match should be accepted
     * @return <tt>true</tt> if the string is matched,
     *         <tt>false</tt> otherwise
     */
    private static boolean match(final Context ctxt,
                                 final Block re,
                                 final int[] str,
                                 final int idxStartTxt,
                                 final int idx,
                                 final int idxEndTxt,
                                 final boolean acceptPartialMatch)
        throws Fatal.Exception {
        int idxTxt = idx;
        int c;

        final int nbGroups = re.get(Str.NUM_GROUPS).asLong();
        final Str.ReGroup[] groups = new ReGroup[nbGroups];
        for (int i = 0; i < nbGroups; i++) {
            groups[i] = new Str.ReGroup();
        } // end for
        final int nbRegisters = re.get(Str.NUM_REGISTERS).asLong();
        final int[] registers = new int[nbRegisters];
        for (int i = 0; i < nbRegisters; i++) {
            registers[i] = Str.NULL;
        } // end for
        ctxt.registerSlot(Str.SLOT_GROUPS, groups);

        BacktrackPoint back = null;
        int pc = 0;
        final List<BacktrackPoint> stack = new LinkedList<BacktrackPoint>(); // stack top is at start of list
        final Block cpool = re.get(Str.CPOOL).asBlock();
        final Block normTable = re.get(Str.NORM_TABLE).asBlock();
        groups[0].idxStart = idxTxt;

        while (true) {
            final int instr = re.get(0).asBlock().get(pc++).asLong();
            int gto = Str.NO_GOTO;
            switch (opcode(instr)) {
            case Str.CHAR:
                if (idxTxt == idxEndTxt) {
                    gto = Str.GOTO_PREFIX_MATCH;
                    break;
                } else if (str[idxTxt] != arg(instr)) {
                    gto = Str.GOTO_BACKTRACK;
                    break;
                } else {
                    idxTxt++;
                } // end if/elsif/else
                break;
            case Str.CHARNORM:
                if (idxTxt == idxEndTxt) {
                    gto = Str.GOTO_PREFIX_MATCH;
                    break;
                } else if (normTable.getUnsignedByte(str[idxTxt]) != arg(instr)) {
                    gto = Str.GOTO_BACKTRACK;
                    break;
                } else {
                    idxTxt++;
                } // end if/elsif/else
                break;
            case Str.STRING: {
                final int[] s = cpool.get(arg(instr)).asBlock().getUnsignedBytes();
                int i = 0;
                c = i < s.length ? s[i++] : 0;
                while (c != 0) {
                    if (idxTxt == idxEndTxt) {
                        gto = Str.GOTO_PREFIX_MATCH;
                        break;
                    } else if (c != str[idxTxt]) {
                        gto = Str.GOTO_BACKTRACK;
                        break;
                    } else {
                        idxTxt++;
                    } // end if/elsif/else
                    c = i < s.length ? s[i++] : 0;
                } // end while
                break;
            } // end case
            case Str.STRINGNORM: {
                final int[] s = cpool.get(arg(instr)).asBlock().getUnsignedBytes();
                int i = 0;
                c = i < s.length ? s[i++] : 0;
                while (c != 0) {
                    if (idxTxt == idxEndTxt) {
                        gto = Str.GOTO_PREFIX_MATCH;
                        break;
                    } else if (c != normTable.getUnsignedByte(str[idxTxt])) {
                        gto = Str.GOTO_BACKTRACK;
                        break;
                    } else {
                        idxTxt++;
                    } // end if/elsif/else
                    c = i < s.length ? s[i++] : 0;
                } // end while
                break;
            } // end case
            case Str.CHARCLASS:
                if (idxTxt == idxEndTxt) {
                    gto = Str.GOTO_PREFIX_MATCH;
                    break;
                } // end if
                c = str[idxTxt];
                if (!inBitSet(cpool.get(arg(instr)).asBlock().getUnsignedBytes(), str[idxTxt])) {
                    gto = Str.GOTO_BACKTRACK;
                    break;
                } // end if
                idxTxt++;
                break;
            case Str.BOL:
                if ((idxTxt > idxStartTxt) && (str[idxTxt - 1] != Str.END_OF_LINE)) {
                    gto = Str.GOTO_BACKTRACK;
                } // end if
                break;
            case Str.EOL:
                if ((idxTxt < idxEndTxt) && (str[idxTxt] != Str.END_OF_LINE)) {
                    gto = Str.GOTO_BACKTRACK;
                } // end if
                break;
            case Str.WORDBOUNDARY:
                if (idxTxt == idxStartTxt) {
                    if (idxTxt == idxEndTxt) {
                        gto = Str.GOTO_PREFIX_MATCH;
                        break;
                    } // end if
                    if (isWordLetter(str[idxTxt])) {
                        break;
                    } // end if/elsif
                    gto = Str.GOTO_BACKTRACK;
                    break;
                } else if (idxTxt == idxEndTxt) {
                    if (isWordLetter(str[idxTxt - 1])) {
                        break;
                    } // end if
                    gto = Str.GOTO_BACKTRACK;
                    break;
                } else {
                    if (isWordLetter(str[idxTxt - 1]) != isWordLetter(str[idxTxt])) {
                        break;
                    } // end if
                    gto = Str.GOTO_BACKTRACK;
                    break;
                } // end if/elsif/else
            case Str.BEGGROUP: {
                final int groupNo = arg(instr);
                final ReGroup group = groups[groupNo];
                back = BacktrackPoint.makeUndo((groupNo << 2) | BacktrackPoint.START_TAG, group.idxStart);
                group.idxStart = idxTxt;
                gto = Str.GOTO_PUSH;
                break;
            } // end case
            case Str.ENDGROUP: {
                final int groupNo = arg(instr);
                final ReGroup group = groups[groupNo];
                back = BacktrackPoint.makeUndo((groupNo << 2) | BacktrackPoint.END_TAG, group.idxEnd);
                group.idxEnd = idxTxt;
                gto = Str.GOTO_PUSH;
                break;
            } // end case
            case Str.REFGROUP: {
                final Str.ReGroup group = groups[arg(instr)];
                if ((group.idxStart == Str.NULL)
                    || (group.idxEnd == Str.NULL)) {
                    gto = Str.GOTO_BACKTRACK;
                } else {
                    for (int s = group.idxStart; s < group.idxEnd; s++) {
                        if (idxTxt == idxEndTxt) {
                            gto = Str.GOTO_PREFIX_MATCH;
                            break;
                        } else if (str[s] != str[idxTxt]) {
                            gto = Str.GOTO_BACKTRACK;
                            break;
                        } else {
                            idxTxt++;
                        } // end if/elsif/else
                    } // end for
                } // end if/else
                break;
            } // end case
            case Str.ACCEPT:
                gto = Str.GOTO_ACCEPT;
                break;
            case Str.SIMPLEOPT: {
                final int[] set = cpool.get(arg(instr)).asBlock().getUnsignedBytes();
                if (idxTxt < idxEndTxt) {
                    c = str[idxTxt];
                    if (inBitSet(set, str[idxTxt])) {
                        idxTxt++;
                    } // end if
                } // end if
                break;
            } // end case
            case Str.SIMPLESTAR: {
                final int[] set = cpool.get(arg(instr)).asBlock().getUnsignedBytes();
                while ((idxTxt < idxEndTxt) && inBitSet(set, str[idxTxt])) {
                    c = str[idxTxt];
                    idxTxt++;
                } // end while
                if (idxTxt < idxEndTxt) {
                    c = str[idxTxt];
                } // end if
                break;
            } // end case
            case Str.SIMPLEPLUS: {
                final int[] set = cpool.get(arg(instr)).asBlock().getUnsignedBytes();
                if (idxTxt == idxEndTxt) {
                    gto = Str.GOTO_PREFIX_MATCH;
                    break;
                } // end if
                c = str[idxTxt];
                if (!inBitSet(set, str[idxTxt])) {
                    gto = Str.GOTO_BACKTRACK;
                } else {
                    idxTxt++;
                    while ((idxTxt < idxEndTxt) && inBitSet(set, str[idxTxt])) {
                        c = str[idxTxt];
                        idxTxt++;
                    } // end while
                    if (idxTxt < idxEndTxt) {
                        c = str[idxTxt];
                    } // end if
                } // end if/else
                break;
            } // end case
            case Str.GOTO:
                pc += signedArg(instr);
                break;
            case Str.PUSHBACK:
                back = BacktrackPoint.makePos(pc + signedArg(instr), idxTxt);
                gto = Str.GOTO_PUSH;
                break;
            case Str.SETMARK: {
                final int regNo = arg(instr);
                back = BacktrackPoint.makeUndo((regNo << 2) | BacktrackPoint.REGISTER_TAG, registers[regNo]);
                registers[regNo] = idxTxt;
                gto = Str.GOTO_PUSH;
                break;
            } // end case
            case Str.CHECKPROGRESS: {
                if (registers[arg(instr)] == idxTxt) {
                    gto = Str.GOTO_BACKTRACK;
                } // end if
                break;
            } // end case
            default:
                Fatal.raise("impossible case in re_match");
                break;
            } // end switch
            while (gto != Str.NO_GOTO) {
                switch (gto) {
                case Str.GOTO_PUSH:
                    stack.add(0, back);
                    gto = Str.NO_GOTO;
                    break;
                case Str.GOTO_PREFIX_MATCH:
                    if (acceptPartialMatch) {
                        gto = Str.GOTO_ACCEPT;
                    } else {
                        gto = Str.GOTO_BACKTRACK;
                    } // end if/else
                    break;
                case Str.GOTO_BACKTRACK:
                    gto = Str.NO_GOTO;
                    while (true) {
                        if (stack.size() == 0) {
                            return false;
                        } // end if
                        final BacktrackPoint pt = stack.remove(0);
                        if (pt.isPos()) {
                            pc = pt.getPc();
                            idxTxt = pt.getTxt();
                            break;
                        } else {
                            final int loc = pt.getLoc();
                            final int val = pt.getVal();
                            switch (loc & 3) {
                            case BacktrackPoint.START_TAG:
                                groups[loc >> 2].idxStart = val;
                                break;
                            case BacktrackPoint.END_TAG:
                                groups[loc >> 2].idxEnd = val;
                                break;
                            case BacktrackPoint.REGISTER_TAG:
                                registers[loc >> 2] = val;
                                break;
                            default:
                                assert false : "invalid backtrack tag";
                            } // end switch
                        } // end if/else
                    } // end while
                    break;
                case Str.GOTO_ACCEPT:
                    stack.clear();
                    groups[0].idxEnd = idxTxt;
                    return true;
                default:
                    assert false : "invalid goto";
                } // end switch
            } // end while
        } // end while
    } // end method 'match(Context, Block, int[], int, int, int, boolean)'

    /**
     * Allocates groups as an ocaml value.
     * @param ctxt context
     * @param re regular expression
     * @return matched groups as an ocaml value
     */
    private static Value allocGroups(final Context ctxt, final Block re) {
        final ReGroup[] groups =
            (Str.ReGroup[]) ctxt.getSlot(Str.SLOT_GROUPS);
        final int n = re.get(Str.NUM_GROUPS).asLong();
        final Block res = Block.createBlock(n * 2, 0);
        for (int i = 0; i < n; i++) {
            final ReGroup group = groups[i];
            if ((group.idxStart == Str.NULL) || (group.idxEnd == Str.NULL)) {
                res.set(2 * i, Str.NULL_VALUE);
                res.set(2 * i + 1, Str.NULL_VALUE);
            } else {
                res.set(2 * i, Value.createFromLong(group.idxStart));
                res.set(2 * i + 1, Value.createFromLong(group.idxEnd));
            } // end if/else
        } // end for
        return Value.createFromBlock(res);
    } // end method 'allocGroups(Context, Block)'

    /**
     * Tests whether a string matches a regular expression.
     * @param ctxt context
     * @param re compiled regular expression
     * @param str string to test
     * @param pos position in string
     * @return an array of matched groups (empty array if no match)
     * @throws Fail.Exception if passed position is invalid
     */
    @Primitive
    public static Value re_string_match(final CodeRunner ctxt,
                                        final Value re,
                                        final Value str,
                                        final Value pos)
        throws Fail.Exception, Fatal.Exception {
        final Context context = ctxt.getContext();
        final Block reBlock = re.asBlock();
        final int[] b = str.asBlock().getUnsignedBytes();
        final int idxStartTxt = 0;
        final int idxTxt = pos.asLong();
        final int idxEndTxt = b.length;

        if ((idxTxt < idxStartTxt) || (idxTxt > idxEndTxt)) {
            Fail.invalidArgument("Str.string_match");
        } // end if
        if (match(context, reBlock, b, idxStartTxt, idxTxt, idxEndTxt, false)) {
            return allocGroups(context, reBlock);
        } else {
            return ctxt.getContext().getAtom(0);
        } // end if/else
    } // end method 're_string_match(CodeRunner, Value, Value, Value)'

    /**
     * Tests whether a string partially matches a regular expression.
     * @param ctxt context
     * @param re compiled regular expression
     * @param str string to test
     * @param pos position in string
     * @return an array of matched groups (empty array if no match)
     */
    @Primitive
    public static Value re_partial_match(final CodeRunner ctxt,
                                         final Value re,
                                         final Value str,
                                         final Value pos)
        throws Fail.Exception, Fatal.Exception {
        final Context context = ctxt.getContext();
        final Block reBlock = re.asBlock();
        final int[] b = str.asBlock().getUnsignedBytes();
        final int idxStartTxt = 0;
        final int idxTxt = pos.asLong();
        final int idxEndTxt = b.length;

        if ((idxTxt < idxStartTxt) || (idxTxt > idxEndTxt)) {
            Fail.invalidArgument("Str.string_partial_match");
        } // end if
        if (match(context, reBlock, b, idxStartTxt, idxTxt, idxEndTxt, true)) {
            return allocGroups(context, reBlock);
        } else {
            return ctxt.getContext().getAtom(0);
        } // end if/else
    } // end method 're_partial_match(CodeRunner, Value, Value, Value)'

    /**
     * Tests whether a string matches a regular expression (forward).
     * @param ctxt context
     * @param re compiled regular expression
     * @param str string to test
     * @param startPos position in string
     * @return an array of matched groups (empty array if no match)
     */
    @Primitive
    public static Value re_search_forward(final CodeRunner ctxt,
                                          final Value re,
                                          final Value str,
                                          final Value startPos)
        throws Fail.Exception, Fatal.Exception {
        final Context context = ctxt.getContext();
        final Block reBlock = re.asBlock();
        final int[] b = str.asBlock().getUnsignedBytes();
        final int idxStartTxt = 0;
        int idxTxt = startPos.asLong();
        final int idxEndTxt = b.length;

        if ((idxTxt < idxStartTxt) || (idxTxt > idxEndTxt)) {
            Fail.invalidArgument("Str.search_forward");
        } // end if
        if (reBlock.get(START_CHARS) == NULL_VALUE) {
            do {
                if (match(context, reBlock, b, idxStartTxt, idxTxt, idxEndTxt, false)) {
                    return allocGroups(context, reBlock);
                } // end if
                idxTxt++;
            } while (idxTxt <= idxEndTxt);
            return ctxt.getContext().getAtom(0);
        } else {
            final int[] startChars = reBlock.get(CPOOL).asBlock().get(reBlock.get(START_CHARS).asLong()).asBlock().getUnsignedBytes();
            do {
                while ((idxTxt < idxEndTxt)
                       && (startChars[b[idxTxt]] == 0)) {
                    idxTxt++;
                } // end while
                if (match(context, reBlock, b, idxStartTxt, idxTxt, idxEndTxt, false)) {
                    return allocGroups(context, reBlock);
                } // end if
                idxTxt++;
            } while (idxTxt <= idxEndTxt);
            return ctxt.getContext().getAtom(0);
        } // end if/else
    } // end method 're_search_forward(CodeRunner, Value, Value, Value)'

    /**
     * Tests whether a string matches a regular expression (backward).
     * @param ctxt context
     * @param re compiled regular expression
     * @param str string to test
     * @param startPos position in string
     * @return an array of matched groups (empty array if no match)
     */
    @Primitive
    public static Value re_search_backward(final CodeRunner ctxt,
                                           final Value re,
                                           final Value str,
                                           final Value startPos)
        throws Fail.Exception, Fatal.Exception {
        final Context context = ctxt.getContext();
        final Block reBlock = re.asBlock();
        final int[] b = str.asBlock().getUnsignedBytes();
        final int idxStartTxt = 0;
        int idxTxt = startPos.asLong();
        final int idxEndTxt = b.length;

        if ((idxTxt < idxStartTxt) || (idxTxt > idxEndTxt)) {
            Fail.invalidArgument("Str.search_backward");
        } // end if
        if (reBlock.get(START_CHARS) == NULL_VALUE) {
            do {
                if (match(context, reBlock, b, idxStartTxt, idxTxt, idxEndTxt, false)) {
                    return allocGroups(context, reBlock);
                } // end if
                idxTxt--;
            } while (idxTxt >= idxStartTxt);
            return ctxt.getContext().getAtom(0);
        } else {
            final int[] startChars = reBlock.get(CPOOL).asBlock().get(reBlock.get(START_CHARS).asLong()).asBlock().getUnsignedBytes();
            do {
                while ((idxTxt > idxStartTxt)
                       && (startChars[b[idxTxt]] == 0)) {
                    idxTxt--;
                } // end while
                if (match(context, reBlock, b, idxStartTxt, idxTxt, idxEndTxt, false)) {
                    return allocGroups(context, reBlock);
                } // end if
                idxTxt--;
            } while (idxTxt >= idxStartTxt);
            return ctxt.getContext().getAtom(0);
        } // end if/else
    } // end method 're_search_backward(CodeRunner, Value, Value, Value)'

    /**
     * Replaces portions of text.
     * @param ctxt context
     * @param repl string to replace portions in
     * @param groups array of matched groups
     * @param orig matched string
     */
    @Primitive
    public static Value re_replacement_text(final CodeRunner ctxt,
                                            final Value repl,
                                            final Value groups,
                                            final Value orig)
        throws Fail.Exception {
        int len = 0;
        final String replString = repl.asBlock().asString();
        int p = 0;
        int n = replString.length();
        final Block grp = groups.asBlock();
        final String origin = orig.asBlock().asString();
        while (n > 0) {
            char c = replString.charAt(p++);
            n--;
            if (c != '\\') {
                len++;
            } else {
                if (n == 0) {
                    Fail.failWith("Str.replace: illegal backslash sequence");
                } // end if
                c = replString.charAt(p++);
                n--;
                switch (c) {
                case '\\':
                    len++;
                    break;
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    final int d = (c - '0') * 2;
                    if (d >= grp.getWoSize()) {
                        Fail.failWith("Str.replace: reference to unmatched group");
                    } // end if
                    final int start = grp.get(d).asLong();
                    final int end = grp.get(d + 1).asLong();
                    if (start == - 1) {
                        Fail.failWith("Str.replace: reference to unmatched group");
                    } // end if
                    len += end - start;
                    break;
                default:
                    len += 2;
                    break;
                } // end switch
            } // end if/else
        } // end while

        final StringBuilder res = new StringBuilder(len);
        p = 0;
        n = replString.length();
        while (n > 0) {
            char c = replString.charAt(p++);
            n--;
            if (c != '\\') {
                res.append(c);
            } else {
                c = replString.charAt(p++);
                n--;
                switch (c) {
                case '\\':
                    res.append('\\');
                    break;
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    final int d = 2 * (c - '0');
                    final int start = grp.get(d).asLong();
                    final int end = grp.get(d + 1).asLong();
                    len  = end - start;
                    res.append(origin.substring(start, len));
                    break;
                default:
                    res.append('\\');
                    res.append(c);
                    break;
                } // end switch
            } // end if/else
        } // end while
        return Value.createFromBlock(Block.createString(res.toString()));
    } // end method 're_replacement_text(CodeRunner, Value, Value, Value)'

} // end class 'Str'
